package Algorithm.binaryTree;

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution3 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addFirst(root);
        List<List<Integer>> result = new ArrayList();
        int level = 0;
        int n = 0;
        while (0 != (n=queue.size())){
            List levelResult = new ArrayList();
            if (level%2==0){
                for (int i=0;i<n;i++){
                    TreeNode temp = queue.removeLast();
                    if (temp.left!=null){
                        queue.addFirst(temp.left);
                    }
                    if (temp.right!=null){
                        queue.addFirst(temp.right);
                    }
                    levelResult.add(temp);
                }
            }else {
                for (int i=0;i<n;i++){
                    TreeNode temp = queue.removeFirst();
                    if (temp.right!=null){
                        queue.addLast(temp.right);
                    }
                    if (temp.left!=null){
                        queue.addLast(temp.left);
                    }
                    levelResult.add(temp);
                }
            }
            level++;
            System.out.println("level:"+level+" "+levelResult.size());
            result.add(levelResult);
        }

        return result;
    }
}
